home *** CD-ROM | disk | FTP | other *** search
/ Light ROM 1 / LIGHT-ROM 1 (Amiga Library Services)(1994).iso / ffdisks / d966.lha / UChessSrc / UChessSrc.lha / search.c < prev    next >
C/C++ Source or Header  |  1994-02-11  |  46KB  |  1,765 lines
  1. /*
  2.  * search.c - C source for GNU CHESS
  3.  *
  4.  * Copyright (c) 1988,1989,1990 John Stanback Copyright (c) 1992 Free Software
  5.  * Foundation
  6.  *
  7.  * This file is part of GNU CHESS.
  8.  *
  9.  * GNU Chess is free software; you can redistribute it and/or modify it under
  10.  * the terms of the GNU General Public License as published by the Free
  11.  * Software Foundation; either version 2, or (at your option) any later
  12.  * version.
  13.  *
  14.  * GNU Chess is distributed in the hope that it will be useful, but WITHOUT ANY
  15.  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  16.  * FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
  17.  * details.
  18.  *
  19.  * You should have received a copy of the GNU General Public License along with
  20.  * GNU Chess; see the file COPYING.  If not, write to the Free Software
  21.  * Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  22.  */
  23. #include "gnuchess.h"
  24.  
  25. #define ZEROALLBETWEENPLY 1
  26.  
  27. #ifdef QUIETBACKGROUND
  28. short __aligned background = 0;
  29.  
  30. #endif /* QUIETBACKGROUND */
  31. static short int __aligned DepthBeyond;
  32. short __aligned Threat[MAXDEPTH];
  33. unsigned short int __aligned PrVar[MAXDEPTH];
  34. extern short int ISZERO;
  35. extern long EADD,EGET;
  36. extern char mvstr[4][6];
  37. extern short int recycle;
  38. extern int trying_again;
  39. int got_20000=0;
  40. short __aligned ThreatSave[MAXDEPTH]; /* tom@izf.tno.nl */
  41. extern short __aligned QueenCheck[MAXDEPTH]; /* tom@izf.tno.nl */
  42. #ifdef NULLMOVE
  43. short int __aligned no_null;
  44. short int __aligned null;         /* Null-move already made or not */
  45. short int __aligned PVari;        /* Is this the PV */
  46. #endif
  47. #ifdef DEBUG40
  48. extern int whichway;
  49. #endif
  50. #ifdef DEBUG
  51. unsigned short __aligned DBLINE[MAXDEPTH];
  52. struct leaf __aligned *dbptr;
  53.  
  54. #endif
  55. short __aligned start_stage;
  56. short __aligned thrashing_tt; /* must we recycle slots at random. TomV */
  57. short int __aligned zwndw;
  58.  
  59. #include "ataks3.h"
  60.  
  61. #define __USE_SYSBASE
  62. #include <proto/exec.h>
  63.  
  64. extern long OrigResponse;
  65. extern int global_tmp_score;
  66. extern int previous_score;
  67. short __aligned myflagpvs=true;
  68. int __aligned backsrchaborted=0;
  69. int __aligned Sdepth2=0;
  70. extern int MoveNowOK;
  71. extern int procpri;
  72. extern struct Process *myproc;
  73.  
  74.  
  75. #ifdef SPEED_PRECALC
  76. unsigned short __aligned PreCalcedHint;
  77. unsigned short __aligned PreCalcedMove;
  78. int DoPreCalc (unsigned INTSIZE *, INTSIZE);
  79. #endif
  80. int __aligned Castled[2]={0,0};
  81. int __aligned myEnPassant[2]={0,0};
  82.  
  83.  
  84.  
  85. inline short int repetition (void);
  86.  
  87.  
  88. #include "debug41.h"
  89. /* ............    MOVE GENERATION & SEARCH ROUTINES    .............. */
  90.  
  91. inline
  92. short int
  93. repetition ()
  94.  
  95. /*  Check for draw by threefold repetition.  */
  96.  
  97. {
  98.   register short i, c,cnt;
  99.   register unsigned short m;
  100.   short b[64];
  101.  
  102.   cnt = c = 0;
  103.   /* try to avoid work */
  104.   if (GameCnt > Game50 + 4)
  105.     {
  106. #if defined(NOMEMSET) || defined(MSDOS)
  107.       for (i = 0; i < 64; b[i++] = 0);
  108. #else
  109. #ifndef AMIGA
  110.       memset ((char *) b, 0, (unsigned long)sizeof (b));
  111. #else
  112.       ClearMem(b,sizeof (b));
  113. #endif
  114. #endif /* NOMEMSET */
  115.       for (i = GameCnt; i >= Game50; i--)
  116.     {
  117.       m = GameList[i].gmove;
  118.       /* does piece exist on diff board? */
  119.       if (b[m & 0x3f])
  120.         {
  121.           /* does diffs cancel out, piece back? */
  122.           if ((b[m >> 8] += b[m & 0x3f]) == 0)
  123.         --c;
  124.           b[m & 0x3f] = 0;
  125.         }
  126.       else
  127.         {
  128.           /* create diff */
  129.           ++c;
  130.           /* does diff cancel out another diff? */
  131.           if (!(b[m >> 8] -= (b[m & 0x3f] = board[m & 0x3f] +
  132.                   (color[m & 0x3f] << 8))))
  133.         --c;
  134.         }
  135.       /* if diff count is 0 we have a repetition */
  136.       if (c == 0)
  137.         if ((i ^ GameCnt) & 1)
  138.           cnt++;
  139.     }
  140.     }
  141.     return cnt;
  142. }
  143.  
  144. int plyscore, globalscore;
  145. int
  146. pick (short int p1, short int p2)
  147.  
  148. /*
  149.  * Find the best move in the tree between indexes p1 and p2. Swap the best
  150.  * move into the p1 element.
  151.  *
  152.  */
  153. {
  154.   register struct leaf *p, *q, *r, *k;
  155.   register s0;
  156.   struct leaf temp;
  157.  
  158.   k = p = &Tree[p1];
  159.   q = &Tree[p2];
  160.   s0 = p->score;
  161.   for (r = p + 1; r <= q; r++)
  162.     if ((r->score) > s0)
  163.       {
  164.     s0 = (r->score);
  165.     p = r;
  166.       }
  167.   if (p != k)
  168.     {
  169.       temp = *p;
  170.       *p = *k;
  171.       *k = temp;
  172.       return true;
  173.     }
  174.   return false;
  175. }
  176.  
  177. #ifdef DEBUG
  178. unsigned short trace[MAXDEPTH];
  179. char traceline[256];
  180. unsigned short tracelog[MAXDEPTH];
  181. int tracen = 0;
  182. int traceflag = 0;
  183. int traceply = 0;
  184. #endif
  185. int __aligned bookflag = false;
  186. int __aligned Jscore = 0;
  187.  
  188. static int __aligned TCcount, TCleft;
  189. void
  190. SelectMove (short int side, short int iop)
  191.  
  192.  
  193. /*
  194.  * Select a move by calling function search() at progressively deeper ply
  195.  * until time is up or a mate or draw is reached. An alpha-beta window of
  196.  * -Awindow to +Bwindow points is set around the score returned from the
  197.  * previous iteration. If Sdepth != 0 then the program has correctly
  198.  * predicted the opponents move and the search will start at a depth of
  199.  * Sdepth+1 rather than a depth of 1.
  200.  */
  201.  
  202. {
  203.   static short int i, tempb, tempc, tempsf, tempst, xside, rpt;
  204.   static short int alpha, beta, score;
  205.   static struct GameRec *g;
  206.   int earlyflag;
  207.   char mystr[16];
  208.   short InChkDummy;
  209.   short start_score;
  210. #ifdef DEBUG
  211.  
  212. if(debuglevel & (512|1024)){
  213.     char b[32];
  214.     short c1,c2,r1,r2;
  215. tracen=0;
  216. traceflag = false;
  217. traceply = 0;
  218. tracelog[0]=0;
  219. while(true){
  220.     /*printf("debug?");
  221.     gets(b);*/
  222.     if(b[0] == 'p')traceply = atoi(&b[1]);
  223.     else
  224.     if(b[0] == '\0')break;
  225.     else{
  226.         c1 = b[0] - 'a';
  227.               r1 = b[1] - '1';
  228.               c2 = b[2] - 'a';
  229.               r2 = b[3] - '1';
  230.               trace[++tracen] = (locn (r1, c1) << 8) | locn (r2, c2);
  231.     }
  232.     if(tracen == 0 && traceply >0)traceflag = true;
  233.     }
  234.     
  235. }
  236. #endif
  237.  
  238. //  InitializeStats(); // MY FIX FOR UNDO PROBLEMS!!! TMP!!!
  239.  
  240. got_20000 = 0;
  241. start_again:
  242.   flag.timeout = false;
  243.   flag.back = flag.musttimeout = false;
  244.   xside = side ^ 1;
  245.   recycle = (GameCnt % rehash) - rehash;
  246.   /* if background mode set to infinite */
  247.   if (iop == 2)
  248.     {
  249.       (void)SetTaskPri((struct Task *)myproc,0);
  250.       OrigResponse = ResponseTime = 9999999;
  251. #ifdef QUIETBACKGROUND
  252.       background = true;
  253. #endif /* QUIETBACKGROUND */
  254.     }
  255.   else
  256.     {
  257.       player = side;
  258.       if (TCflag)
  259.     {
  260.       TCcount = 0;
  261. #ifdef QUIETBACKGROUND
  262.       background = false;
  263. #endif /* QUIETBACKGROUND */
  264.       if (TimeControl.moves[side] < 1)
  265.         TimeControl.moves[side] = 1;
  266.       /* special case time per move specified */
  267.       if (flag.onemove)
  268.         {
  269.           OrigResponse = ResponseTime = TimeControl.clock[side] - 100;
  270.           TCleft = 0;
  271.         }
  272.       else
  273.         {
  274.           /* calculate avg time per move remaining */
  275.           TimeControl.clock[side] += TCadd;
  276.  
  277.           ResponseTime = (TimeControl.clock[side]) / (((TimeControl.moves[side]) * 2) + 1);
  278.           TCleft = (int)ResponseTime / 3;
  279.           ResponseTime += TCadd/2;
  280.           if (TimeControl.moves[side] < 5)
  281.         TCcount = MAXTCCOUNTX - 1;
  282.         }
  283.       if (ResponseTime < 101)
  284.         {
  285.           ResponseTime = 100;
  286.           TCcount = MAXTCCOUNTX;
  287.         }
  288.       else if (ResponseTime < 200)
  289.         {
  290.           TCcount = MAXTCCOUNTX - 1;
  291.         }
  292.           OrigResponse = ResponseTime;
  293.           if ((TimeControl.moves[side] > 9))
  294.            ResponseTime += 51;
  295. //           ResponseTime = ResponseTime + (ResponseTime/4); // ADDED TO 2.50 to make clock better
  296.     }
  297.       else
  298.        {
  299. #ifdef QUIETBACKGROUND
  300.       background = false;
  301. #endif /* QUIETBACKGROUND */
  302.     OrigResponse = ResponseTime = MaxResponseTime;
  303.        }
  304.       if (TCleft)
  305.     {
  306.       TCcount = ((int)((TimeControl.clock[side] - ResponseTime)) / 2) / TCleft;
  307.       if (TCcount > MAXTCCOUNTX)
  308.         TCcount = 0;
  309.       else
  310.         TCcount = MAXTCCOUNTX - TCcount;
  311.     }
  312.       else
  313.     TCcount = MAXTCCOUNTX;
  314.     }
  315.  
  316.   if (MoveNowOK)
  317.    {
  318.     thinking2 = 1; /* allow move now menu item to work */
  319.    }
  320.   else
  321.    {
  322.     thinking2 = 0; /* do not allow move now menu item to work */
  323.    }
  324. #ifndef OLD_LOOKAHEAD // this is faster for predicted moves
  325. //sprintf(mystr,"sd2 %d",Sdepth);
  326. //ShowMessage(mystr);
  327.   if (Sdepth > 0) // guessed correct move!
  328.    {
  329.      if (TCflag)
  330.        time0 = time(0L);
  331. #ifdef QUIETBACKGROUND
  332.     if (!background)
  333. #endif /* QUIETBACKGROUND */
  334.      SearchStartStuff (side);
  335.     trying_again = 0;
  336.     if ((GameCnt>2)&&(TCflag)&&(global_tmp_score >= (previous_score-50))&&(Sdepth >= GlobalTgtDepth)
  337.           &&(global_tmp_score >= (GameList[GameCnt-1].score - 50)))
  338.      {
  339.       if (Sdepth >= (GameList[GameCnt-1].depth))
  340.        flag.timeout = true;
  341.       goto ForceTheMove2;
  342.      }
  343.     if ((TCflag)||(backsrchaborted))
  344.      {
  345.       goto ForceTheMove2; // for now use 2, it was ForceTheMove before
  346.      }
  347.     else
  348.      {
  349.       goto ForceTheMove2;
  350.      }
  351.    }
  352. #endif
  353.   ExtraTime = 0;
  354.   ExaminePosition ();
  355. //  score = ScorePosition (side);
  356.   stage= -1; /* Force init in UpdateWeights() */
  357.   start_score= Tscore[0]= Tscore[1]= score=
  358.     evaluate (side, 1, 1, 0, -9999, 9999, 0, &InChkDummy);
  359.   start_stage= stage;
  360. #ifdef QUIETBACKGROUND
  361.   if (!background)
  362. #endif /* QUIETBACKGROUND */
  363.     ShowSidetoMove ();
  364. #ifdef notdef
  365.   if (TCflag && TCcount < MAXTCCOUNT)
  366.     if (score < SCORETIME)
  367.       {
  368.     ExtraTime += TCleft;
  369.     TCcount++;
  370.       }
  371. #endif
  372.  
  373. #ifdef QUIETBACKGROUND
  374.   if (!background)
  375. #endif /* QUIETBACKGROUND */
  376.     SearchStartStuff (side);
  377. #ifdef HISTORY
  378. #if defined(NOMEMSET) || defined(MSDOS)
  379.   for (i = 0; i < 32768; i++)
  380.     history[i] = 0;
  381. #else
  382. #ifndef AMIGA
  383.   memset ((unsigned char *) history, 0, (unsigned long)sizeof (history));
  384. #else
  385.   ClearMem(history,sizeof (history));
  386. #endif
  387. #endif /* NOMEMSET */
  388. #endif
  389.   FROMsquare = TOsquare = -1;
  390.   PV = 0;
  391.   if (iop == 1)
  392.     hint = 0;
  393. #ifndef AMIGA
  394.   for (i = 0; i < MAXDEPTH; i++)
  395.    {
  396.     PrVar[i] = killr0[i] = killr1[i] = killr2[i] = killr3[i] = 0;
  397.    }
  398. #else
  399.   ClearMem(PrVar,MAXDEPTH*sizeof(PrVar[0]));
  400.   ClearMem(killr0,MAXDEPTH*sizeof(killr0[0]));
  401.   ClearMem(killr1,MAXDEPTH*sizeof(killr1[0]));
  402.   ClearMem(killr2,MAXDEPTH*sizeof(killr2[0]));
  403.   ClearMem(killr3,MAXDEPTH*sizeof(killr3[0]));
  404. #endif
  405.   /* set initial window for search */
  406.   alpha = score - ((computer == black) ? BAwindow : WAwindow);
  407.   beta = score + ((computer == black) ? BBwindow : WBwindow);
  408.   rpt = 0;
  409.   TrPnt[1] = 0;
  410.   root = &Tree[0];
  411.   MoveList (side, 1);
  412.   for (i = TrPnt[1]; i < TrPnt[2]; i++)
  413.     if (!pick (i, TrPnt[2] - 1))
  414.       break;
  415.   /* can I get a book move? */
  416.   if ((flag.regularstart && Book))
  417.     {
  418.       flag.timeout = bookflag = OpeningBook (&hint, side);
  419.       if (TCflag)
  420.        {
  421.     ResponseTime += ResponseTime;
  422.         OrigResponse = ResponseTime;
  423.        }
  424.     }
  425. #ifdef SPEED_PRECALC
  426.   if ((!flag.timeout)&&(ThinkAheadWorked))
  427.    {
  428.     flag.timeout = DoPreCalc(&hint,side);
  429.    }
  430. #endif
  431.   /* zero stats for hash table */
  432. #ifdef ZEROALLBETWEENPLY
  433.   if (!bookflag)
  434.    {
  435.     ZeroTTable();
  436.     EADD = EGET = 0;
  437.    }
  438. #endif
  439.   reminus = replus = 0;
  440.   GenCnt = NodeCnt = ETnodes = EvalNodes = HashCnt = FHashAdd = HashAdd = FHashCnt = THashCol = HashCol = 0;
  441.   globalscore = plyscore = score;
  442.   zwndw = 20;
  443.   Jscore = trying_again = global_tmp_score = previous_score = 0;
  444. #include "debug4.h"
  445.   /********************* main loop ********************************/
  446.     Sdepth = (MaxSearchDepth<(MINDEPTH-1))?MaxSearchDepth:(MINDEPTH-1);
  447. /*printf("\n\n");*/
  448. ForceTheMove:
  449.   while (!flag.timeout)
  450.     {
  451. /*printf("time0 = %d et = %d SDepth = %d GameCnt = %d\n",time0, et,Sdepth,GameCnt);*/
  452. /*printf("ThinkAheadWorked = %d  ThinkAheadDepth = %d\n",ThinkAheadWorked,ThinkAheadDepth);*/
  453.       /* go down a level at a time */
  454.       Sdepth++;
  455. #ifdef NULLMOVE
  456.       null = 0;
  457.       PVari = 1;
  458. #endif
  459. //      DepthBeyond = Sdepth + ((Sdepth == 1) ? 7 : 11);
  460.       DepthBeyond = Sdepth +
  461.         ((Sdepth == 1) ? FBEYOND : flag.threat ? SBEYOND: TBEYOND);
  462.       no_null= (emtl[xside] == 0 || emtl[side] == 0);
  463.  
  464. #if !defined CHESSTOOL && !defined XBOARD
  465. #ifdef QUIETBACKGROUND
  466.       if (!background)
  467. #endif /* QUIETBACKGROUND */
  468.     ShowDepth (' ');
  469. #endif
  470.       root->score= Tscore[0]= Tscore[1]= start_score;
  471.       /* search at this level returns score of PV */
  472. //      score = search (side, 1, Sdepth, alpha, beta, PrVar, &rpt, QBLOCK);
  473.       score = search (side, 1, Sdepth, 0, alpha, beta, PrVar, &rpt, QBLOCK, false);
  474.       /* save PV as killer */
  475.       for (i = 1; i <= Sdepth; i++)
  476.     killr0[i] = PrVar[i];
  477.  
  478.       /* low search failure re-search with (-inf,score) limits  */
  479.       if (score < alpha)
  480.     {
  481. #if !defined CHESSTOOL && !defined XBOARD
  482.       reminus++;
  483. #ifdef QUIETBACKGROUND
  484.       if (!background)
  485. #endif /* QUIETBACKGROUND */
  486.         ShowDepth ('-');
  487. #endif
  488.       if (TCflag && TCcount < MAXTCCOUNTR)
  489.         {
  490.           TCcount = MAXTCCOUNTR - 1;
  491.           ExtraTime += (8 * TCleft);
  492.         }
  493. //      score = search (side, 1, Sdepth, -9999, 9999, PrVar, &rpt, QBLOCK); // was -99999, 9999
  494.           root->score= Tscore[0]= Tscore[1]= start_score;
  495.       score = search (side, 1, Sdepth, 0, -9999, 9999, PrVar, &rpt,QBLOCK,false);
  496.     }
  497.       /* high search failure re-search with (score, +inf) limits */
  498.       if (score > beta && !(root->flags & exact))
  499.     {
  500. #if !defined CHESSTOOL && !defined XBOARD
  501.       replus++;
  502. #ifdef QUIETBACKGROUND
  503.       if (!background)
  504. #endif /* QUIETBACKGROUND */
  505.         ShowDepth ('+');
  506. #endif
  507.           root->score= Tscore[0]= Tscore[1]= start_score;
  508.       score = search (side, 1, Sdepth, 0, -9999, 9999, PrVar, &rpt,QBLOCK,false);
  509.     }
  510.       /**************** out of search ********************************************/
  511. ForceTheMove2:
  512.       if ((flag.timeout)||(flag.musttimeout)||(flag.back))
  513.        earlyflag = true;
  514.       else
  515.        earlyflag = false;
  516.       if (flag.musttimeout || Sdepth >= MaxSearchDepth)
  517.        {
  518.     flag.timeout = true;
  519.        }
  520.       else if (TCflag && (Sdepth > (MINDEPTH - 1)) && (TCcount < MAXTCCOUNTR))
  521.     {
  522.       if (killr0[1] != PrVar[1] /* || Killr0[2] != PrVar[2] */ )
  523.         {
  524.           TCcount++;
  525.           ExtraTime += TCleft;
  526.         }
  527.       if ((abs (score - globalscore) / Sdepth) > ZDELTA)
  528.         {
  529.           TCcount++;
  530.           ExtraTime += TCleft;
  531.         }
  532.     }
  533.       if (score > (Jscore - zwndw) && score > (Tree[1].score + 250)) ExtraTime = 0;
  534. /*printf("sdepth = %d mindepth = %d TCflag = %d \n4*et = %d respt = %d extra = %d\n",Sdepth,MINDEPTH,TCflag,4*et,ResponseTime,ExtraTime);*/
  535.       if (root->flags & exact) flag.timeout = true;
  536.       /*else if (Tree[1].score < -9000) flag.timeout = true;*/
  537.       else if (!(Sdepth < MINDEPTH) && TCflag && ((4 * et) > (2*ResponseTime + ExtraTime))) flag.timeout = true;
  538.       /************************ time control ***********************************/
  539.  
  540.       /* save PV as killer */
  541.       for (i = 1; i <= Sdepth + 1; i++) killr0[i] = PrVar[i];
  542.       if (!flag.timeout) start_score = Tscore[0] = score;
  543.       /* if (!flag.timeout) */
  544. //      for (i = TrPnt[1]+1; i < TrPnt[2]; i++) if (!pick (i, TrPnt[2] - 1)) break;
  545.       /* if done or nothing good to look at quit */
  546.       if ((root->flags & exact) || (score < -9000)) flag.timeout = true;
  547.       /* find the next best move put below root */
  548. #include "debug13.h"
  549.       if (!flag.timeout)
  550.     {
  551.       /* */
  552. #if !defined NODYNALPHA
  553.       Jscore = (plyscore + score) >> 1;
  554. #endif
  555.       zwndw = 20 + abs (Jscore / 12);
  556.       plyscore = score;
  557.       /* recompute search window */
  558.       beta = score + ((computer == black) ? BBwindow : WBwindow);
  559. #if !defined NODYNALPHA
  560.       alpha = ((Jscore < score) ? Jscore : score) - ((computer == black) ? BAwindow : WAwindow) - zwndw;
  561. #else
  562.       alpha = score - ((computer == black) ? BAwindow : WAwindow);
  563. #endif
  564.     }
  565. #if !defined CHESSTOOL && !defined XBOARD
  566. #ifdef QUIETBACKGROUND
  567.       if (!background)
  568. #endif /* QUIETBACKGROUND */
  569.     ShowResults (score, PrVar, '.');
  570. #ifdef DEBUG41
  571.       debug41 (score, PrVar, '.');
  572. #endif
  573. #endif
  574. #include "debug16.h"
  575.       if ((score >= 11000)&&(!got_20000))
  576.        {
  577.         got_20000 = 1;
  578.         Sdepth = 0;
  579.         goto start_again;
  580.        }
  581.       if ((((!PrVar[1])||(!PrVar[2]))&&(!(root->flags & exact))&&(iop != 2)&&(abs(score) < 9000))) /* do not trust this move! */
  582.        {
  583.         if ((Sdepth > 2))
  584.          {
  585.           if ((earlyflag))
  586.            {
  587.             Sdepth--;
  588.            }
  589.           if (!trying_again)
  590.            { /* this is first bogus move we have seen */
  591.             ResponseTime = ResponseTime << 1;
  592.             ExtraTime += 251;
  593.            }
  594.           else
  595.            { /* this is not 1st bogus move we have seen */
  596.             ExtraTime += 201;
  597.            }
  598.           trying_again = 1;
  599.           flag.timeout = false;
  600.           flag.back = false;
  601.           flag.musttimeout = false;
  602.          }
  603.        }
  604.       else if (trying_again) /* this move is trustworthy, to an extent */
  605.        {
  606.         if ((TCflag && ((4 * et) > (ResponseTime + ExtraTime - 251)))||(root->flags & exact)) 
  607.          flag.timeout = true;
  608.        }
  609.       previous_score = score;
  610.     } /* while !flag.timeout */
  611.   /******************************* end of main loop ***********************************/
  612.   /* background mode */
  613.   if (iop == 2)
  614.    {
  615.     if (bookflag) Sdepth = 0;
  616.     if (!flag.easy)
  617.      {
  618.       Sdepth2 = Sdepth;
  619.       if (Sdepth2 > (GlobalTgtDepth+1))
  620.        Sdepth2--;
  621. #ifdef SPEED_PRECALC
  622.       PreCalcedMove = (Tree[TrPnt[1]].f << 8) | (Tree[TrPnt[1]].t);
  623.       PreCalcedHint = ((PrVar[1]) ? PrVar[2] : 0);
  624. #endif
  625.      }
  626.     return;
  627.    }
  628. #include "debug4.h"
  629.   if (rpt >= 2)
  630.     {
  631.       root->flags |= draw;
  632.       DRAW = CP[101];        /* Repetition */
  633.     }
  634.   else
  635.     /* if no moves and not in check then draw */
  636.   if ((score == -9999) && !(SqAtakd3 (PieceList[side][0], xside)))
  637.     {
  638.       root->flags |= draw;
  639.       DRAW = CP[87];        /* No moves */
  640.     }
  641.   else if (GameCnt == MAXMOVES)
  642.     {
  643.       root->flags |= draw;
  644.       DRAW = CP[80];        /* Max Moves */
  645.     }
  646.   /* not in book so set hint to guessed move for other side */
  647.   if (!bookflag)
  648.     hint = ((PrVar[1]) ? PrVar[2] : 0);
  649.  
  650.   /* if not mate or draw make move and output it */
  651.   if (((score > -9999) && (rpt <= 2)) || (root->flags & draw))
  652.     {
  653.       MakeMove (side, &Tree[0], &tempb, &tempc, &tempsf, &tempst, &INCscore);
  654. #if !defined NOMATERIAL
  655.       if (flag.material && !pmtl[black] && !pmtl[white] && (mtl[white] < (valueR + valueK)) && (mtl[black] < (valueR + valueK)))
  656.     {
  657.       root->flags |= draw;
  658.       DRAW = CP[224];    /* No pieces */
  659.     }
  660.       else
  661. #endif
  662.       if (!PieceCnt[black] && !PieceCnt[white])
  663.     {
  664.       root->flags |= draw;
  665.       DRAW = CP[88];    /* No pieces */
  666.     }
  667.       algbr (root->f, root->t, (short) root->flags);
  668.     }
  669.   else
  670.     {
  671.       algbr (0, 0, 0);        /* Zero move string when mate. */
  672.       root->score = score;    /* When mate, ignore distinctions!
  673.                  * --SMC */
  674.     }
  675.   g = &GameList[GameCnt];
  676.   if (g->flags & capture && g->piece == king)
  677.     {
  678.       flag.mate = flag.illegal = true;
  679.     }
  680.   /* If Time Control get the elapsed time */
  681.   if (TCflag)
  682.     ElapsedTime (1);
  683.   /* if mate set flag */
  684.   if ((score == -9999 || score == 9999))
  685.     flag.mate = true;
  686.   OutputMove (mystr);
  687.   /* if mate clear hint */
  688.   if (flag.mate)
  689.     hint = 0;
  690.   /* if pawn move or capture or castle or promote zero repitition array */
  691.   if ((board[root->t] == pawn) || (root->flags & (capture | cstlmask | promote)))
  692.     {
  693.       Game50 = GameCnt;
  694.       ZeroRPT ();
  695.     }
  696.   /* add move to game list */
  697.   g->score = score;
  698.   g->nodes = NodeCnt;
  699.   g->time = (et +50)/100;
  700.   g->depth = Sdepth;
  701. #include "debug40.h"
  702.   /* update time comtrol info */
  703.   if (TCflag)
  704.     {
  705. #if defined CHESSTOOL || defined XBOARD
  706.       TimeControl.clock[side] -= (et + OperatorTime + 45);
  707.       timecomp[compptr] = (et + OperatorTime + 45);
  708. #else
  709.       TimeControl.clock[side] -= (et + OperatorTime);
  710.       timecomp[compptr] = (et + OperatorTime);
  711. #endif
  712.       /* finished our required moves - setup the next set */
  713.       --TimeControl.moves[side];
  714.     }
  715.   /* check for end conditions */
  716.   if ((root->flags & draw) /* && flag.bothsides */ )
  717. #if !defined CLIENT
  718.      flag.mate = true;
  719. #else 
  720.     ;
  721. #endif
  722.   else if (GameCnt == MAXMOVES)
  723.     {
  724.       flag.mate = true;
  725.     }
  726.   /* out of move store, you loose */
  727.   else
  728.     /* switch to other side */
  729.     player = xside;
  730.   Sdepth = 0;
  731. }
  732.  
  733. int
  734. search (short int side,
  735.     register short int ply,
  736.     register short int depth,
  737.     short ext,
  738.     short int alpha,
  739.     short int beta,
  740.     short unsigned int *bstline,
  741.     short int *rpt,
  742.         short SAVEHT,
  743.     int didnull)
  744.  
  745. /*
  746.  * Perform an alpha-beta search to determine the score for the current board
  747.  * position. If depth <= 0 only capturing moves, pawn promotions and
  748.  * responses to check are generated and searched, otherwise all moves are
  749.  * processed. The search depth is modified for check evasions, certain
  750.  * re-captures and threats. Extensions may continue for up to 11 ply beyond
  751.  * the nominal search depth.
  752.  */
  753.  
  754.  
  755. {
  756.   register short j, pnt;
  757.   short tempb, tempc, tempsf, tempst;
  758.   short xside, pbst, score, rcnt, InChk;
  759.   unsigned short mv, nxtline[MAXDEPTH];
  760.   struct leaf *node, tmp;
  761.   short best = -12000;
  762.   short bestwidth = 0;
  763. #ifdef NULLMOVE
  764. #ifndef OLD_NULL
  765.   short int PVsave;
  766. #endif
  767.   short int PVarisave;
  768. #endif
  769. #ifdef DEBUG
  770.   int xxxtmp;
  771.   int tracetmp;
  772. #endif
  773.   short extdb= 0;
  774.   short threat= 0;      /* tom@izf.tno.nl */
  775.   short threat2= 0;     /* tom@izf.tno.nl */
  776.   short do_pvs;
  777.  
  778.   NodeCnt++;
  779.   /* look every ZNODE nodes for a timeout */
  780.   if (!null)
  781.    {
  782.   if (NodeCnt > ETnodes )
  783.     {
  784.       ElapsedTime (2);
  785.       if (flag.back)
  786.     {
  787.       flag.back = false;
  788.       flag.timeout = true;
  789.       flag.musttimeout = false;
  790.     }
  791.       else if (TCflag || MaxResponseTime)
  792.     {
  793.       if ((et >= (ResponseTime + ExtraTime)) && Sdepth > MINDEPTH && abs(best) < 10000)
  794.         {            /* try to extend to finish ply */
  795. #define TRYEXTEND 1
  796. #ifdef TRYEXTEND
  797.           if ((TCflag && TCcount < MAXTCCOUNTX)&&(GameCnt > 29))
  798.         {
  799.           flag.musttimeout = true;
  800.           TCcount += 1;
  801.           ExtraTime += TCleft;
  802.         }
  803.           else
  804.         {
  805.           flag.timeout = true;
  806.           flag.musttimeout = false;
  807.         }
  808. #else
  809.           if ((TCflag && TCcount < MAXTCCOUNTX)&&(flag.easy))
  810.         {
  811.           flag.musttimeout = true;
  812.           TCcount += 1;
  813.           ExtraTime += TCleft;
  814.         }
  815.           else
  816.         {
  817.           flag.timeout = true;
  818.           flag.musttimeout = false;
  819.         }
  820. #endif
  821.         }
  822.     }
  823.     }
  824.   else if (!TCflag && flag.musttimeout && Sdepth > MINDEPTH)
  825.     {
  826.       flag.timeout = true;
  827.       flag.musttimeout = false;
  828.     }
  829.    } // !null
  830.   xside = side ^ 1;
  831.   if (ply == 1) INCscore = 0; // TMP!! MY Fix for INCscore not init at ply 1
  832.   /* slk is lone king indicator for either side */
  833.   score = evaluate (side, ply, depth, ext, alpha, beta, INCscore, &InChk);
  834.  
  835.   /*
  836.    * check for possible repitition if so call repitition - rpt is
  837.    * repeat count
  838.    */
  839.   if ((ply <= Sdepth + 3) && rpthash[side][hashkey & 0xFF] > 0)
  840.     {
  841.       *rpt = repetition ();
  842.  
  843.       /*
  844.        * repeat position >2 don't need to return score it's taken
  845.        * care of above
  846.        */
  847.       if (*rpt == 1) score /= 2;
  848.     }
  849.   else
  850.     *rpt = 0;
  851.  
  852.   /* score > 9000 its a draw or mate */
  853.   if (score > 9000 || root->flags & draw)
  854.     {
  855.       bstline[ply] = 0;
  856.       return (score);
  857.     }
  858.   /* Do we need to add depth because of special conditions */
  859.   /* if in check or pawn threat or in capture sequence search deeper */
  860.   /*************************************** depth extensions ***********************************/
  861. #ifdef OLDEXT
  862.   if (depth > 0)
  863.     {
  864.       /* Allow opponent a chance to check again */
  865.       if (InChk)
  866.     depth = (depth < 2) ? 2 : depth;
  867.       else if (PawnThreat[ply - 1] ||
  868.            (flag.rcptr && (score > alpha) &&
  869.       (score < beta) && (ply > 2) && CptrFlag[ply - 1] && CptrFlag[ply - 2]))
  870.     ++depth;
  871.     }
  872.   else
  873.     {
  874.       if (score >= alpha &&
  875.       (InChk || PawnThreat[ply - 1] || (hung[side] > 1 /* && ply == Sdepth + 1*/)))
  876.     depth = 1;
  877.       else if (score <= beta &&
  878.            ((ply < Sdepth + 4) && (ply > 4) &&
  879.  
  880.         ChkFlag[ply - 2] && ChkFlag[ply - 4]))
  881.     {
  882.               depth = 1;
  883.         }
  884.     }
  885. #else
  886.  
  887. #define DOTHREAT    (start_stage < THRSTAGE)
  888. #define DOCHECK     (start_stage < CHECKSTAGE)
  889.  
  890.   Threat[ply]= 0;
  891.   if (depth > 0)
  892.     {
  893.       /* Allow opponent a chance to check again */
  894.       if (InChk) {
  895.           if (flag.threat)
  896.             depth= DOCHECK && (ply+depth<DepthBeyond-DEPTHMARGIN) ?
  897.               depth+1: depth;
  898.           else
  899.             depth= (depth < 2) ? 2 : depth;
  900.       }
  901.       else if ((ply>1 && PawnThreat[ply - 1] && ply+depth<DepthBeyond-DEPTHMARGIN) ||                                        
  902.                (flag.rcptr && ply>2 && CptrFlag[ply - 1] && CptrFlag[ply - 2] &&               ((ply<Sdepth+2 && CptrFlag[ply-1]==CptrFlag[ply-2]) ||
  903.                (score > alpha && score < beta)))
  904.                )
  905.           ++depth;
  906.     }
  907.   else
  908.     { 
  909.       if (score >= alpha &&
  910.           (InChk || (ply>1 && PawnThreat[ply - 1] && depth<DepthBeyond-4)
  911.           || (hung[side] > 1 && !ext))) {
  912.         threat2= 1;
  913.         ext++;
  914.         depth= 1;
  915.       }
  916.       else if (score <= beta &&
  917.                ((ply<Sdepth+4 && ply>4 &&
  918.                 ChkFlag[ply-2] && ChkFlag[ply-4] &&
  919.                 (ChkFlag[ply-2] != ChkFlag[ply-4] ||
  920.                 (flag.threat && DOTHREAT && QueenCheck[ply-2])))
  921.           ||
  922.                 (flag.threat && ply<DepthBeyond-DEPTHMARGIN && ply>6
  923.                 && ChkFlag[ply-2] && ChkFlag[ply-4] && ChkFlag[ply-6]
  924.                 && ((ply < Sdepth+4 ?
  925.                   (ChkFlag[ply-2] != ChkFlag[ply-4] || ChkFlag[ply-2] != ChkFlag[ply-6])
  926.                   : (ChkFlag[ply-2] != ChkFlag[ply-4] &&
  927.                      ChkFlag[ply-2] != ChkFlag[ply-6] &&
  928.                      ChkFlag[ply-4] != ChkFlag[ply-6]))
  929.                 || (DOTHREAT && QueenCheck[ply-2]
  930.                 && QueenCheck[ply-4] && QueenCheck[ply-6]
  931.                 && QueenCheck[ply-2] != QueenCheck[ply-6]))
  932.                 ))) {
  933.           depth= 1;
  934.           ext++;
  935.           Threat[ply]= threat= 1;
  936.         }
  937.     }    
  938.   ThreatSave[ply]= ((ply>1 && ThreatSave[ply-1]) || threat);
  939. #endif
  940.   /*******************************************************************************************/
  941.   /* try the local transition table if it's there */
  942. #if ttblsz
  943.   if (/*depth > 0 &&*/ flag.hash && ply > 1)
  944.     {
  945.       if (ProbeTTable (side, depth, ply, &alpha, &beta, &score) == true)
  946.     {
  947.       bstline[ply] = PV;
  948.       bstline[ply + 1] = 0;
  949. #include "debug64.h"
  950.       if (beta == -20000)
  951.         return (score);
  952.       if (alpha > beta)
  953.         return (alpha);
  954.     }
  955. #ifdef HASHFILE
  956.       /* ok try the transition file if its there */
  957.       else if (hashfile && (depth > HashDepth) && (GameCnt < HashMoveLimit)
  958.      && (ProbeFTable (side, depth, ply, &alpha, &beta, &score) == true))
  959.     {
  960. #ifdef notdef
  961.       int hgood = false;
  962.       int f = PV >> 8;
  963.       int t = PV & 0x3f;
  964.       register int i;
  965.  
  966.       /*
  967.        * if you find something put it in the local table
  968.        * for future reference
  969.        */
  970.       hgood = false;
  971.       for (i = TrPnt[ply]; i < TrPnt[ply + 1]; i++)
  972.         {
  973.           if (Tree[i].f == f && Tree[i].t == t)
  974.         {
  975.           hgood = true;
  976.           break;
  977.         }
  978.         }
  979.       if (hgood)
  980.         {
  981. #endif
  982.           PutInTTable (side, score, depth, ply, alpha, beta, PV);
  983.           bstline[ply] = PV;
  984.           bstline[ply + 1] = 0;
  985.           if (beta == -20000)
  986.         return (score);
  987.           if (alpha > beta)
  988.         return (alpha);
  989. #ifdef notdef
  990.         }
  991. #endif
  992. #include "debug10.h"
  993.     }
  994. #endif /* HASHFILE */
  995.     }
  996. #endif /* ttblsz */
  997.  
  998.   if (ply>1) TrPnt[ply+1]= TrPnt[ply]; // TMP!! My Fix for move gen
  999.  
  1000.   /*
  1001.    * if more then DepthBeyond ply past goal depth or at goal depth and
  1002.    * score > beta quit - means we are out of the window
  1003.    */
  1004.   if (ply > DepthBeyond || (depth < 1 && score > beta))
  1005.     {
  1006.       return (score);
  1007.     }
  1008.  
  1009.   /*
  1010.    * if below first ply and not at goal depth generate all moves else
  1011.    * only capture moves
  1012.    */
  1013.   if (ply > 1)
  1014.     if (depth > 0  /*|| ply<(SDEPTHLIM)*/||  // ply < sdlim was in 4pl66
  1015.     (background && ply<Sdepth + 2))
  1016.       {
  1017.     MoveList (side, ply);
  1018. // next line is NEW from 4pl67
  1019.       if (TrPnt[ply] == TrPnt[ply + 1]) { if(!InChk) return ((side==computer)?contempt:-contempt); else return (-10001+ply); }
  1020.       }
  1021.     else{
  1022.       CaptureList (side, ply);
  1023.       SAVEHT = false;
  1024.     }
  1025.  
  1026.   /* no moves return what we have */
  1027.  
  1028.   /*
  1029.    * normally a search will continue til past goal and no more capture
  1030.    * moves exist
  1031.    */
  1032.   /* unless it hits DepthBeyond */
  1033.   if (TrPnt[ply] == TrPnt[ply + 1])
  1034.     {
  1035.       return (score);
  1036.     }
  1037.  
  1038.  
  1039.  
  1040.   /* if not at goal set best = -inf else current score */
  1041.      best = (depth >0) ? -12000:score;
  1042. #ifdef NULLMOVE
  1043.  
  1044.   PVarisave = PVari;
  1045. #ifndef OLD_NULL
  1046.   if (!null &&                         /* no previous null-move */
  1047.       !PVari &&                        /* no null-move during the PV */
  1048.       (ply > 2) &&
  1049.       (ply <= Sdepth) &&                       /* not at ply 1 */
  1050.       (depth > 3) &&                   /* not during the quienscesearch */
  1051.       !InChk &&                        /* no check */
  1052.       ((mtl[side] + mtl[xside]) > NULLMOVELIM))
  1053. #else
  1054.   if (!null &&                         /* no previous null-move */
  1055.       !PVari &&                        /* no null-move during the PV */
  1056.       (ply > 1) &                       /* not at ply 1 */
  1057.       (depth > 1) &&                   /* not during the quienscesearch */
  1058.       !InChk &&                        /* no check */
  1059.       ((mtl[side] + mtl[xside]) > NULLMOVELIM))
  1060. #endif
  1061.     /* enough material such that zugzwang is unlike but who knows which value
  1062.        is suitable? */
  1063.     {
  1064.       
  1065.       /* ok, we make a null move, i.e.  this means we have nothing to do
  1066.       but we have to keep the some arrays up to date otherwise gnuchess
  1067.       gets confused.  Maybe somebody knows exactly which informations are
  1068.      important and which not.
  1069.  
  1070.      Another idea is that we try the null-move first and generate the
  1071.      moves later.  This may save time but we have to take care that
  1072.      PV and other variables contain the right value so that the move
  1073.      ordering works right.
  1074.      */
  1075.       register struct GameRec *g;
  1076.       
  1077.       nxtline[ply + 1] = 0;
  1078.       CptrFlag[ply] = 0;
  1079.       PawnThreat[ply] = 0;
  1080.       Tscore[ply] = score;
  1081. #ifndef OLD_NULL
  1082.       PVsave = PV;
  1083.       PV = 0;
  1084. #endif
  1085.       null = 1;
  1086.       g = &GameList[++GameCnt];
  1087.       g->hashkey = hashkey;
  1088.       g->hashbd = hashbd;
  1089.       epsquare = -1;
  1090.       TOsquare = -1;
  1091.       g->Game50 = Game50;
  1092. #ifdef LONGINTS
  1093.       g->gmove = 0xffffffff;
  1094. #else
  1095.       g->gmove = 0xffff;
  1096. #endif
  1097.       g->flags = 0;
  1098.       g->piece = 0;
  1099.       g->color = neutral;
  1100.       
  1101.       best = -search (xside, ply + 1, false, depth - 2, -beta - 1, -beta, nxtline, &rcnt,false,false);
  1102.       null = 0;
  1103. #ifndef OLD_NULL
  1104.       PV = PVsave;
  1105. #endif
  1106.       GameCnt--;
  1107.       if (best < alpha) best = -12000;
  1108.       else if (best > 0 && best > beta) return (best);
  1109.       else
  1110.      best = -12000;
  1111.     }
  1112. #endif
  1113.   /* if best so far is better than alpha set alpha to best */
  1114.     if(best>alpha)alpha=best;
  1115.   /********************** main loop ************************************************************************/
  1116.   /* look at each move until no more or beta cutoff */
  1117.    do_pvs = 0;
  1118. //   for (pnt = pbst = TrPnt[ply]; pnt < TrPnt[ply + 1] &&
  1119. //    (best <= beta || (ply == 1 && best > 9000)); pnt++) /* Find best mate, TomV TMP!!*/
  1120.   for (pnt = pbst = TrPnt[ply]; pnt < TrPnt[ply + 1] && best <= beta; pnt++)
  1121.     {
  1122.       /* find the most interesting looking of the remaining moves */
  1123.       if (ply > 1)
  1124.     pick (pnt, TrPnt[ply + 1] - 1);
  1125. #ifdef NULLMOVE
  1126.       PVari = PVarisave && (pnt == TrPnt[ply]);  /* Is this the PV? */
  1127. #endif
  1128.  
  1129.       node = &Tree[pnt];
  1130.       /* is this a forbidden move */
  1131.       if (pnt == pbst)
  1132.         do_pvs= myflagpvs && !null && (PrVar[ply] == ((node->f << 8) | node->t));
  1133.       if (ply == 1 && node->score == -32768)
  1134.     continue;
  1135. #ifdef DEBUG
  1136.     if(debuglevel & (512 | 1024)){
  1137.         if(!tracen)traceflag = ((ply >traceply)?false:true);
  1138.          else
  1139.         if(ply <= tracen && (ply ==1 || traceflag))
  1140.             { 
  1141.             if(trace[ply] == (Tree[pnt].t |(Tree[pnt].f<<8))) traceflag = true; else traceflag = false; }
  1142.         tracelog[ply] = (Tree[pnt].t |(Tree[pnt].f<<8));
  1143.         tracelog[ply+1] = 0;
  1144. }
  1145. #endif
  1146.       nxtline[ply + 1] = 0;
  1147.  
  1148. #if !defined CHESSTOOL && !defined XBOARD
  1149.       /* if at top level */
  1150.       if (ply == 1)
  1151.     {            /* at the top update search status */
  1152.       if (flag.post)
  1153. #ifdef QUIETBACKGROUND
  1154.         if (!background)
  1155. #endif /* QUIETBACKGROUND */
  1156.           ShowCurrentMove (pnt, node->f, node->t);
  1157.     }
  1158. #endif
  1159.       /* make the move and go deeper */
  1160.       MakeMove (side, node, &tempb, &tempc, &tempsf, &tempst, &INCscore);
  1161.       CptrFlag[ply] = (node->flags & capture);
  1162.       PawnThreat[ply] = (node->flags & pwnthrt);
  1163.       Tscore[ply] = node->score;
  1164.       PV = node->reply;
  1165. #ifdef DEBUG
  1166.       xxxtmp = node->score;
  1167.       tracetmp = traceflag;
  1168. #endif
  1169.       if (do_pvs) {
  1170.             if (pbst == pnt) {
  1171.               node->score= -search (xside, ply + 1,
  1172.                                  depth > 0 ? depth - 1 : 0, ext,
  1173.                                  -beta, -alpha,
  1174.                                  nxtline, &rcnt,SAVEHT, 0);
  1175.             } else {
  1176.               node->score= -search(xside, ply + 1,
  1177.                               depth > 0 ? depth - 1 : 0, ext,
  1178.                               -alpha-1, -alpha,
  1179.                               nxtline, &rcnt,SAVEHT, 0);
  1180.               if (node->score >= best && alpha <= node->score
  1181.               && node->score <= beta)
  1182.                   node->score = -search (xside, ply + 1,
  1183.                                  depth > 0 ? depth - 1 : 0, ext,
  1184.                                  -beta, -node->score,
  1185.                                  nxtline, &rcnt,SAVEHT, 0);
  1186.             }
  1187.           } else
  1188.  
  1189.       node->score = -search (xside, ply + 1,
  1190.                  (depth > 0) ? depth - 1 : 0, ext,
  1191.                  -beta, -alpha,
  1192.                  nxtline, &rcnt, SAVEHT, false);
  1193.       node->width = (ply % 2 == 1) ? (TrPnt[ply + 2] - TrPnt[ply + 1]) : 0;
  1194.       if (abs (node->score) > 9000) node->flags |= exact;
  1195.       else if (rcnt == 1) node->score /= 2;
  1196.       if(node->score == (9999-ply) && !ChkFlag[ply] ) {node->flags |= draw;
  1197.           node->score = ((side == computer) ? contempt : -contempt);}
  1198. #include "debug256.h"
  1199.       if ((rcnt >= 2 || GameCnt - Game50 > 99 
  1200. /*|| (node->score == 9999 - ply && !ChkFlag[ply])*/
  1201.           ))
  1202.         {
  1203.           node->flags |= (draw | exact);
  1204.           DRAW = CP[58];    /* Draw */
  1205.           node->score = ((side == computer) ? contempt : -contempt);
  1206.         }
  1207.       node->reply = nxtline[ply + 1];
  1208.       /* reset to try next move */
  1209.       UnmakeMove (side, node, &tempb, &tempc, &tempsf, &tempst);
  1210.       /* if best move so far */
  1211.       if (!flag.timeout && ((node->score > best) || ((node->score == best) && (node->width > bestwidth))))
  1212.     {
  1213.       /*
  1214.        * all things being equal pick the denser part of the
  1215.        * tree
  1216.        */
  1217.       bestwidth = node->width;
  1218.  
  1219.       /*
  1220.        * if not at goal depth and better than alpha and not
  1221.        * an exact score increment by depth
  1222.        */
  1223.       if (depth > 0 && node->score > alpha && !(node->flags & exact))
  1224.         node->score += depth;
  1225.       best = node->score;
  1226.       pbst = pnt;
  1227.       if (best > alpha) { alpha = best; }
  1228.       /* update best line */
  1229.       for (j = ply + 1; nxtline[j] > 0; j++) bstline[j] = nxtline[j];
  1230.       bstline[j] = 0;
  1231.       bstline[ply] = (node->f << 8) | node->t;
  1232.       /* if at the top */
  1233.       if (ply == 1)
  1234.         {
  1235.           /*
  1236.            * if its better than the root score make it
  1237.            * the root
  1238.            */
  1239.           if ((best > root->score) || ((best == root->score) && (bestwidth > root->width)))
  1240.         {
  1241.           tmp = Tree[pnt];
  1242.           for (j = pnt - 1; j >= 0; j--) Tree[j + 1] = Tree[j];
  1243.           Tree[0] = tmp;
  1244.           pbst = 0;
  1245.         }
  1246.               if (Sdepth > 2)
  1247.                global_tmp_score = best;
  1248. #if !defined CHESSTOOL && !defined XBOARD
  1249. #ifdef QUIETBACKGROUND
  1250.           if (!background)
  1251. #endif /* QUIETBACKGROUND */
  1252.         if (Sdepth > 2)
  1253.           if (best > beta)
  1254.             {
  1255.               ShowResults (best, bstline, '+');
  1256. #ifdef DEBUG41
  1257.               debug41 (best, bstline, '+');
  1258. #endif
  1259.             }
  1260.           else if (best < alpha)
  1261.             {
  1262.               ShowResults (best, bstline, '-');
  1263. #ifdef DEBUG41
  1264.               debug41 (best, bstline, '-');
  1265. #endif
  1266.             }
  1267.           else
  1268.                    {
  1269.             ShowResults (best, bstline, '&');
  1270.                    }
  1271. #ifdef DEBUG41
  1272.           debug41 (best, bstline, '&');
  1273. #endif
  1274. #else
  1275.        if(!background && Sdepth >2 && best < alpha){
  1276.         ExtraTime=8*TCleft;
  1277.        }
  1278. #endif
  1279.         }
  1280.     }
  1281.       if (flag.timeout)
  1282.     {
  1283.           DepthBeyond-= extdb;
  1284. #ifdef NULLMOVE
  1285.   PVari = PVarisave;
  1286. #endif
  1287.       return (Tscore[ply - 1]);
  1288.     }
  1289.     }
  1290.  
  1291.   /******************************************************************************************/
  1292.   node = &Tree[pbst];
  1293.   mv = (node->f << 8) | node->t;
  1294. #ifdef NULLMOVE
  1295.   PVari = PVarisave;
  1296. #endif
  1297. #ifdef DEBUG
  1298. #include "debug512.h"
  1299. #endif
  1300.  
  1301.   /*
  1302.    * we have a move so put it in local table - if it's already there
  1303.    * done else if not there or needs to be updated also put it in
  1304.    * hashfile
  1305.    */
  1306. #if ttblsz
  1307.   if (SAVEHT && flag.hash && ply <= Sdepth && *rpt == 0 && best == alpha)
  1308.     {
  1309. #ifdef notdef
  1310. algbr(node->f,node->t,0);
  1311. /*printf("IN-> %lx %lx %d %d %s\n",hashkey,hashbd,depth,side,mvstr[0]);*/
  1312. #endif
  1313.       if (PutInTTable (side, best, depth, ply, alpha, beta, mv)
  1314. #ifdef HASHFILE
  1315.       && hashfile && (depth > HashDepth) && (GameCnt < HashMoveLimit))
  1316.     {
  1317. #ifdef notdef
  1318. /*printf("FT %d %d %d %x\n",side,best,depth,mv);*/
  1319. #endif
  1320.       PutInFTable (side, best, depth, ply, alpha, beta, node->f, node->t);
  1321.     }
  1322. #else
  1323.     );
  1324. #endif /* HASHFILE */
  1325.     }
  1326. #endif /* ttblsz */
  1327.   if (depth > 0)
  1328.     {
  1329. #ifdef HISTORY
  1330.       j = (node->f << 8) | node->t; // was 6 should be 8
  1331.       if (side == black)
  1332.     j |= 0x4000;
  1333. /*TMPif (j > 32767) { printf("\nBAD HISTORY GUY BAD BAD BAD!!\n");getchar(); }*/
  1334.       if (history[j] < HISTORYLIM)
  1335.     history[j] += (unsigned short) 1<<depth;
  1336. #endif
  1337.       if (node->t != (short)(GameList[GameCnt].gmove & 0xFF))
  1338.     if (best <= beta)
  1339.       killr3[ply] = mv;
  1340.     else if (mv != killr1[ply])
  1341.       {
  1342.         killr2[ply] = killr1[ply];
  1343.         killr1[ply] = mv;
  1344.       }
  1345.       killr0[ply] = ((best > 9000) ? mv : 0);
  1346.     }
  1347.   return (best);
  1348. }
  1349.  
  1350.  
  1351.  
  1352.  
  1353. int
  1354. castle (short int side, short int kf, short int kt, short int iop)
  1355.  
  1356. /* Make or Unmake a castling move. */
  1357.  
  1358. {
  1359.   register short rf, rt, t0, xside;
  1360.  
  1361.   xside = side ^ 1;
  1362.   if (kt > kf)
  1363.     {
  1364.       rf = kf + 3;
  1365.       rt = kt - 1;
  1366.     }
  1367.   else
  1368.     {
  1369.       rf = kf - 4;
  1370.       rt = kt + 1;
  1371.     }
  1372.   if (iop == 0)
  1373.     {
  1374.       if (kf != kingP[side] ||
  1375.       board[kf] != king ||
  1376.       board[rf] != rook ||
  1377.       color[kf] != side ||
  1378.       color[rf] != side ||
  1379.       Mvboard[kf] != 0 ||
  1380.       Mvboard[rf] != 0 ||
  1381.       color[kt] != neutral ||
  1382.       color[rt] != neutral ||
  1383.       color[kt - 1] != neutral ||
  1384.       SqAtakd3 (kf, xside) ||
  1385.       SqAtakd3 (kt, xside) ||
  1386.       SqAtakd3 (rt, xside))
  1387.     return (false);
  1388.     }
  1389.   else
  1390.     {
  1391.       if (iop == 1)
  1392.     {
  1393.           Castled[side] = 1;
  1394.       castld[side] = true;
  1395.       Mvboard[kf]++;
  1396.       Mvboard[rf]++;
  1397.     }
  1398.       else
  1399.     {
  1400.           Castled[side] = 0;
  1401.       castld[side] = false;
  1402.       Mvboard[kf]--;
  1403.       Mvboard[rf]--;
  1404.       t0 = kt;
  1405.       kt = kf;
  1406.       kf = t0;
  1407.       t0 = rt;
  1408.       rt = rf;
  1409.       rf = t0;
  1410.     }
  1411.       board[kt] = king;
  1412.       color[rt] = color[kt] = side;
  1413.       Pindex[kt] = 0;
  1414.       board[kf] = no_piece;
  1415.       color[rf] = color[kf] = neutral;
  1416.       board[rt] = rook;
  1417.       Pindex[rt] = Pindex[rf];
  1418.       board[rf] = no_piece;
  1419.       PieceList[side][Pindex[kt]] = kt;
  1420.       PieceList[side][Pindex[rt]] = rt;
  1421.       UpdateHashbd (side, king, kf, kt);
  1422.       UpdateHashbd (side, rook, rf, rt);
  1423.     }
  1424.   return (true);
  1425. }
  1426.  
  1427.  
  1428. void
  1429. EnPassant (short int xside, short int f, short int t, short int iop)
  1430.  
  1431. /*
  1432.  * Make or unmake an en passant move.
  1433.  */
  1434.  
  1435. {
  1436.   register short l;
  1437.  
  1438.   l = t + ((t > f) ? -8 : 8);
  1439.   if (iop == 1)
  1440.     {
  1441.       myEnPassant[xside] = 1;
  1442.       board[l] = no_piece;
  1443.       color[l] = neutral;
  1444.     }
  1445.   else
  1446.     {
  1447.       board[l] = pawn;
  1448.       color[l] = xside;
  1449.       myEnPassant[xside] = 0;
  1450.     }
  1451.   InitializeStats ();
  1452. }
  1453.  
  1454.  
  1455. void
  1456. UpdatePieceList (short int side, short int sq, short int iop)
  1457.  
  1458. /*
  1459.  * Update the PieceList and Pindex arrays when a piece is captured or when a
  1460.  * capture is unmade.
  1461.  */
  1462.  
  1463. {
  1464.   register short i;
  1465.  
  1466.   if (iop == 1)
  1467.     {
  1468.       PieceCnt[side]--;
  1469.       for (i = Pindex[sq]; i <= PieceCnt[side]; i++)
  1470.     {
  1471.       PieceList[side][i] = PieceList[side][i + 1];
  1472.       Pindex[PieceList[side][i]] = i;
  1473.     }
  1474.     }
  1475.   else
  1476.     {
  1477.       PieceCnt[side]++;
  1478.       PieceList[side][PieceCnt[side]] = sq;
  1479.       Pindex[sq] = PieceCnt[side];
  1480.     }
  1481. }
  1482.  
  1483. void
  1484. MakeMove (short int side,
  1485.       struct leaf *node,
  1486.       short int *tempb,    /* color of to square */
  1487.       short int *tempc,    /* piece at to square */
  1488.       short int *tempsf,    /* static value of piece on from */
  1489.       short int *tempst,    /* static value of piece on to */
  1490.       short int *INCscore)    /* score increment for pawn structure change */
  1491.  
  1492. /*
  1493.  * Update Arrays board[], color[], and Pindex[] to reflect the new board
  1494.  * position obtained after making the move pointed to by node. Also update
  1495.  * miscellaneous stuff that changes when a move is made.
  1496.  */
  1497.  
  1498. {
  1499.   register short f, t, xside, ct, cf;
  1500.   register struct GameRec *g;
  1501.  
  1502.   xside = side ^ 1;
  1503.   g = &GameList[++GameCnt];
  1504.   g->hashkey = hashkey;
  1505.   g->hashbd = hashbd;
  1506.   g->epssq = epsquare;
  1507.   f = node->f;
  1508.   t = node->t;
  1509.   epsquare = -1;
  1510.   /* FROMsquare = f;*/
  1511.   TOsquare = t;
  1512.   *INCscore = 0;
  1513.   g->Game50 = Game50;
  1514.   g->gmove = (f << 8) | t;
  1515.   g->flags = node->flags;
  1516.   if (node->flags & cstlmask)
  1517.     {
  1518.       g->piece = no_piece;
  1519.       g->color = side;
  1520.       (void) castle (side, f, t, 1);
  1521.       Game50 = GameCnt;
  1522.     }
  1523.   else
  1524.     {
  1525.       if (!(node->flags & capture) && (board[f] != pawn))
  1526.     {rpthash[side][hashkey & 0xFF]++;ISZERO++;}
  1527.       else
  1528.     Game50 = GameCnt;
  1529.       *tempsf = svalue[f];
  1530.       *tempst = svalue[t];
  1531.       g->piece = *tempb = board[t];
  1532.       g->color = *tempc = color[t];
  1533.       if (*tempc != neutral)
  1534.     {
  1535.       UpdatePieceList (*tempc, t, 1);
  1536.       /* if capture decrement pawn count */
  1537.       if (*tempb == pawn)
  1538.         {
  1539.           --PawnCnt[*tempc][column (t)];
  1540.         }
  1541.       if (board[f] == pawn)
  1542.         {
  1543.           cf = column (f);
  1544.           ct = column (t);
  1545.           /* move count from from to to */
  1546.           --PawnCnt[side][cf];
  1547.           ++PawnCnt[side][ct];
  1548.  
  1549.           /*
  1550.            * calculate increment for pawn structure
  1551.            * changes
  1552.            */
  1553.           /* doubled or more - */
  1554.           if (PawnCnt[side][ct] > (1 + PawnCnt[side][cf]))
  1555.         *INCscore -= 15;
  1556.           /* went to empty column + */
  1557.           else if (PawnCnt[side][ct] < 1 + PawnCnt[side][cf])
  1558.         *INCscore += 15;
  1559.  
  1560.           /*
  1561.            * went to outside col or empty col on one
  1562.            * side ????????
  1563.            */
  1564.           else if (ct == 0 || ct == 7 || PawnCnt[side][ct + ct - cf] == 0)
  1565.         *INCscore -= 15;
  1566.         }
  1567.       mtl[xside] -= value[*tempb];
  1568.       if (*tempb == pawn)
  1569.         pmtl[xside] -= valueP;
  1570.       UpdateHashbd (xside, *tempb, -1, t);
  1571.       *INCscore += *tempst;
  1572.       Mvboard[t]++;
  1573.     }
  1574.       color[t] = color[f];
  1575.       board[t] = board[f];
  1576.       svalue[t] = svalue[f];
  1577.       Pindex[t] = Pindex[f];
  1578.       PieceList[side][Pindex[t]] = t;
  1579.       color[f] = neutral;
  1580.       board[f] = no_piece;
  1581.       if (board[t] == pawn)
  1582.     if (t - f == 16)
  1583.       epsquare = f + 8;
  1584.     else if (f - t == 16)
  1585.       epsquare = f - 8;
  1586.       if (node->flags & promote)
  1587.     {
  1588.       board[t] = node->flags & pmask;
  1589.       if (board[t] == queen)
  1590.         HasQueen[side]++;
  1591.       else if (board[t] == rook)
  1592.         HasRook[side]++;
  1593.       else if (board[t] == bishop)
  1594.         HasBishop[side]++;
  1595.       else if (board[t] == knight)
  1596.         HasKnight[side]++;
  1597.       --PawnCnt[side][column (t)];
  1598.       mtl[side] += value[board[t]] - valueP;
  1599.       pmtl[side] -= valueP;
  1600.       UpdateHashbd (side, pawn, f, -1);
  1601.       UpdateHashbd (side, board[t], f, -1);
  1602.       *INCscore -= *tempsf;
  1603.     }
  1604.       if (node->flags & epmask)
  1605.     EnPassant (xside, f, t, 1);
  1606.       else
  1607.     UpdateHashbd (side, board[t], f, t);
  1608.       Mvboard[f]++;
  1609.     }
  1610. }
  1611.  
  1612. void
  1613. UnmakeMove (short int side,
  1614.         struct leaf *node,
  1615.         short int *tempb,
  1616.         short int *tempc,
  1617.         short int *tempsf,
  1618.         short int *tempst)
  1619.  
  1620. /*
  1621.  * Take back a move.
  1622.  */
  1623.  
  1624. {
  1625.   register short f, t, xside;
  1626.  
  1627.   xside = side ^ 1;
  1628.   f = node->f;
  1629.   t = node->t;
  1630.   Game50 = GameList[GameCnt].Game50;
  1631.   if (node->flags & cstlmask)
  1632.     (void) castle (side, f, t, 2);
  1633.   else
  1634.     {
  1635.       color[f] = color[t];
  1636.       board[f] = board[t];
  1637.       svalue[f] = *tempsf;
  1638.       Pindex[f] = Pindex[t];
  1639.       PieceList[side][Pindex[f]] = f;
  1640.       color[t] = *tempc;
  1641.       board[t] = *tempb;
  1642.       svalue[t] = *tempst;
  1643.       if (node->flags & promote)
  1644.     {
  1645.       board[f] = pawn;
  1646.       ++PawnCnt[side][column (t)];
  1647.       mtl[side] += valueP - value[node->flags & pmask];
  1648.       pmtl[side] += valueP;
  1649.       UpdateHashbd (side, (short) node->flags & pmask, -1, t);
  1650.       UpdateHashbd (side, pawn, -1, t);
  1651.     }
  1652.       if (*tempc != neutral)
  1653.     {
  1654.       UpdatePieceList (*tempc, t, 2);
  1655.       if (*tempb == pawn)
  1656.         {
  1657.           ++PawnCnt[*tempc][column (t)];
  1658.         }
  1659.       if (board[f] == pawn)
  1660.         {
  1661.           --PawnCnt[side][column (t)];
  1662.           ++PawnCnt[side][column (f)];
  1663.         }
  1664.       mtl[xside] += value[*tempb];
  1665.       if (*tempb == pawn)
  1666.         pmtl[xside] += valueP;
  1667.       UpdateHashbd (xside, *tempb, -1, t);
  1668.       Mvboard[t]--;
  1669.     }
  1670.       if (node->flags & epmask)
  1671.     {
  1672.       EnPassant (xside, f, t, 2);
  1673.     }
  1674.       else
  1675.     UpdateHashbd (side, board[f], f, t);
  1676.       Mvboard[f]--;
  1677.       if (!(node->flags & capture) && (board[f] != pawn))
  1678.     {rpthash[side][hashkey & 0xFF]--;ISZERO--;}
  1679.     }
  1680.   epsquare = GameList[GameCnt--].epssq;
  1681. }
  1682.  
  1683.  
  1684. void
  1685. InitializeStats (void)
  1686.  
  1687. /*
  1688.  * Scan thru the board seeing what's on each square. If a piece is found,
  1689.  * update the variables PieceCnt, PawnCnt, Pindex and PieceList. Also
  1690.  * determine the material for each side and set the hashkey and hashbd
  1691.  * variables to represent the current board position. Array
  1692.  * PieceList[side][indx] contains the location of all the pieces of either
  1693.  * side. Array Pindex[sq] contains the indx into PieceList for a given
  1694.  * square.
  1695.  */
  1696.  
  1697. {
  1698.   register short i, sq;
  1699.  
  1700.   epsquare = -1;
  1701.   for (i = 0; i < 8; i++)
  1702.     {
  1703.       PawnCnt[white][i] = PawnCnt[black][i] = 0;
  1704.     }
  1705.   mtl[white] = mtl[black] = pmtl[white] = pmtl[black] = 0;
  1706.   PieceCnt[white] = PieceCnt[black] = 0;
  1707.   hashbd = hashkey = 0;
  1708.   for (sq = 0; sq < 64; sq++)
  1709.     if (color[sq] != neutral)
  1710.       {
  1711.     mtl[color[sq]] += value[board[sq]];
  1712.     if (board[sq] == pawn)
  1713.       {
  1714.         pmtl[color[sq]] += valueP;
  1715.         ++PawnCnt[color[sq]][column (sq)];
  1716.       }
  1717.     Pindex[sq] = ((board[sq] == king) ? 0 : ++PieceCnt[color[sq]]);
  1718.  
  1719.     PieceList[color[sq]][Pindex[sq]] = sq;
  1720.     hashbd ^= hashcode[color[sq]][board[sq]][sq].bd;
  1721.     hashkey ^= hashcode[color[sq]][board[sq]][sq].key;
  1722.       }
  1723. }
  1724.  
  1725. #ifdef SPEED_PRECALC
  1726.  
  1727. int
  1728. DoPreCalc (unsigned INTSIZE *hint, INTSIZE int side)
  1729.      
  1730. {
  1731.   INTSIZE pnt;
  1732.   unsigned INTSIZE m;
  1733.  
  1734.   int fnd=0;
  1735.  
  1736.   /* if only one just do it */
  1737.   m = PreCalcedMove;
  1738.   /* make sure the move is in the MoveList */
  1739.   for (pnt = TrPnt[1]; pnt < TrPnt[2]; pnt++)
  1740.     {
  1741.       if (((Tree[pnt].f << 8) | Tree[pnt].t) == m)
  1742.     {
  1743.       Tree[pnt].score = 0;
  1744.           fnd = 1;
  1745.       break;
  1746.     }
  1747.     }
  1748.   if (!fnd)
  1749.    return(false);
  1750. #ifdef NEED_CHECK
  1751.   /* Make sure its the best */
  1752.  
  1753.   pick (TrPnt[1], TrPnt[2] - 1);
  1754.   if (Tree[TrPnt[1]].score)
  1755.     {
  1756.       /* no! */
  1757.       return false;
  1758.     }
  1759. #endif
  1760.   /* ok pick up the hint and go */
  1761.   *hint = PreCalcedHint;
  1762.   return true;
  1763. }
  1764. #endif
  1765.